En los capítulos 3 y 4 se abordó la idea de resolver problemas mediante la exploración de un espacio de estados. Dichos estados pueden ser evaluados utilizando heurísticas específicas del dominio y comprobados para ver si son estados objetivo. No obstante, desde la perspectiva del algoritmo de búsqueda, cada estado es visto como una caja negra sin una estructura perceptible interna, y se representa mediante una estructura de datos arbitraria a la que sólo se puede acceder utilizando las rutinas específicas de problema (como la función sucesor, función heurística y el test objetivo). En este capítulo se analizan los problemas de satisfacción de restricciones, cuyos estados y test objetivo se representan de forma simple, estándar y estructurada (sección 5.1). Los algoritmos de búsqueda se definen aprovechando la estructura de los estados y utilizando heurísticas de propósito general en lugar de heurísticas específicas de problema para permitir la resolución de problemas de mayor envergadura (secciones 5.2-5.3). Es importante destacar que la representación estándar del test objetivo revela la estructura del problema (sección 5.4), lo que conduce a métodos de descomposición de problemas y a una comprensión de la conexión entre la estructura del problema y su dificultad de resolución.
La satisfacción de restricciones es un enfoque para resolver problemas que consiste en asignar valores a variables de manera que se satisfagan ciertas restricciones. Cada variable tiene un dominio de valores posibles, y las restricciones especifican qué combinaciones de valores son aceptables para ciertos subconjuntos de variables. Un estado del problema es una asignación de valores a variables, y una solución es una asignación completa que cumple todas las restricciones. Algunos problemas también incluyen una función objetivo que se debe maximizar. Para ilustrar cómo se puede aplicar este enfoque, se considera el problema de colorear un mapa de Australia con tres colores de manera que regiones vecinas no tengan el mismo color. Las variables son las regiones del mapa y sus dominios son los tres colores. Las restricciones se especifican como las combinaciones aceptables de colores para regiones vecinas. La representación del problema como un PSR tiene varias ventajas, como la posibilidad de aplicar métodos de búsqueda estándar y heurísticas genéricas para resolverlo. También se puede simplificar el proceso de solución utilizando la estructura del grafo de restricciones. Los problemas de satisfacción de restricciones más simples implican variables discretas y dominios finitos.
La sección anterior dio una formulación de PSRs como problemas de búsqueda. Usando esta formulación, cualquiera de los algoritmos de búsqueda de los Capítulos 3 y 4 PROBLEMAS DE SATISFACCIÓN DE RESTRICCIONES 159 Figura 5.2 (a) Un problema cripto-aritmético. Cada letra significa un dígito distinto; el objetivo es encontrar una sustitución de las letras por dígitos tal que la suma que resulta es aritméticamente correcta, con la restricción añadida de que no se permite la administración de ceros. (b) El hiper-grafo de restricciones para el problema cripto-aritmético muestra la restricción TodasDif así como las restricciones añadidas en las columnas. Cada restricción es una caja cuadrada relacionada con las variables que restringe. (a) F T U W R O (b) + F T T O W W U O O R X3 X2 X1 PREFERENCIA pueden resolver los PSRs. Suponga que aplicamos la búsqueda primero en anchura a la formulación del PSR genérico de la sección anterior. Rápidamente notamos algo terrible: el factor de ramificación en el nivel superior es de nd, porque cualquiera de los d valores se puede asignar a cualquiera de las n variables. En el siguiente nivel, el factor de ramificación es (n-1)d, etcétera para los n niveles. ¡Generamos un árbol con n! dn hojas, aunque haya sólo dn asignaciones posibles completas! Nuestra formulación del problema, aparentemente razonable pero ingenua, no ha hecho caso de una propiedad crucial común en todos los PSRs: la conmutatividad. Un problema es conmutativo si el orden de aplicación de cualquier conjunto de acciones no tiene ningún efecto sobre el resultado. Éste es el caso de los PSRs porque, asignando valores a variables, alcanzamos la misma asignación parcial sin tener en cuenta el orden. Por lo tanto, todos los algoritmos de búsqueda para el PSR generan los sucesores considerando asignaciones posibles para sólo una variable en cada nodo del árbol de búsqueda. Por ejemplo, en el nodo raíz de un árbol de búsqueda para colorear el mapa de Australia, podríamos tener una opción entre AS rojo, AS verde, y AS azul, pero nunca elegiríamos entre AS rojo y AO azul. Con esta restricción, el número de hojas es dn , como era de esperar. El término búsqueda con vuelta atrás se utiliza para la búsqueda primero en profundidad que elige valores para una variable a la vez y vuelve atrás cuando una variable no tiene ningún valor legal para asignarle. En la Figura 5.3 se muestra este algoritmo. Notemos que usa, en efecto, el método uno a la vez de la generación de sucesor incremental descrita en la página 86. También, extiende la asignación actual para generar un sucesor, más que volver a copiarlo. Como la representación de los PSRs está estandartizada, no hay ninguna necesidad de proporcionar a la BÚSQUEDA-CON-VUELTA-ATRÁS un estado inicial del dominio específico, una función sucesor, o un test del objetivo. En la Figura 5.4 se muestra parte del árbol de búsqueda para el problema de Australia, en donde hemos asignado variables en el orden AO, TN, Q... La vuelta atrás sencilla es un algoritmo sin información en la terminología del Capítulo 3, así que no esperamos que sea muy eficaz para problemas grandes. En la primera columna de la Figura 5.5 se muestran los resultados para algunos problemas y se confirman nuestras expectativas. En el Capítulo 4 remediamos el funcionamiento pobre de los algoritmos de búsqueda sin información suministrándoles funciones heurísticas específicas del dominio obtenidas de nuestro conocimiento del problema. Resulta que podemos resolver los PSRs de manera eficiente sin tal conocimiento específico del dominio. En cambio, encontramos métodos de propósito general que proporcionan las siguientes preguntas: 1. ¿Qué variable debe asignarse después, y en qué orden deberían intentarse sus valores? 2. ¿Cuáles son las implicaciones de las asignaciones de las variables actuales para las otras variables no asignadas? 3. Cuándo un camino falla, es decir, un estado alcanzado en el que una variable no tiene ningún valor legal, ¿puede la búsqueda evitar repetir este fracaso en caminos siguientes? Las subsecciones siguientes contestan a cada una de estas preguntas.
Por defecto, SELECCIONA-VARIABLE-NOASIGNADA simplemente selecciona la siguiente variable no asignada en el orden dado por la lista VARIABLES[psr]. Esta variable estática, rara vez ordenada, da como resultado una búsqueda más eficiente. Por ejemplo, después de las asignaciones para AO rojo y T verde, hay un sólo valor posible para AS, entonces tiene sentido asignar AS azul a continuación más que asignar un valor a Q. De hecho, después de asignar AS, las opciones para Q, NGS, y V están forzadas. Esta idea intuitiva (escoger la variable con menos valores «legales») se llama heurística de mínimos valores restantes (MVR). También llamada heurística «variable más restringida» o «primero en fallar», este último es porque escoge una variable que con mayor probabilidad causará pronto un fracaso, con lo cual podamos el árbol de búsqueda. Si hay una variable X con cero valores legales restantes, la heurística MVR seleccionará X y el fallo será descubierto inmediatamente (evitando búsquedas inútiles por otras variables que siempre fallarán cuando se seleccione X finalmente). La segunda columna de la Figura 5.5, etiquetada con VA MVR, muestra el funcionamiento de esta heurística. El funcionamiento es de tres a 3.000 veces mejor que la vuelta atrás simple, según el problema. Notemos que nuestra medida de rendimiento no hace caso del coste suplementario de calcular los valores heurísticos; la siguiente subsección describe un método que maneja este coste. La heurística MVR no ayuda en absoluto en la elección de la primera región a colorear en Australia, porque al principio cada región tiene tres colores legales. En este caso, el grado heurístico es más práctico. Intenta reducir el factor de ramificación sobre futuras opciones seleccionando la variable, entre las variables no asignadas, que esté implicada en el mayor número de restricciones. En la Figura 5.1, AS es la variable con el grado más alto, cinco; las otras variables tienen grado dos o tres, excepto T, que tiene cero. De hecho, una vez elegida AS, aplicando el grado heurístico que resuelve el problema sin pasos en falso puede elegir cualquier color consistente en cada punto seleccionado y todavía llegar a una solución sin vuelta atrás. La heurística del mínimo de valores restantes es por lo general una guía más poderosa, pero el grado heurístico puede ser útil como un desempate. 162 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO MÍNIMOS VALORES RESTANTES GRADO HEURÍSTICO
Hasta ahora nuestro algoritmo de búsqueda considera las restricciones sobre una variable sólo cuando la variable es elegida por SELECCIONA-VARIABLE-NOASIGNADA. Pero mirando algunas restricciones antes en la búsqueda, o incluso antes de que haya comenzado la búsqueda, podemos reducir drásticamente el espacio de ésta.
Otra manera para usar mejor las restricciones durante la búsqueda se llama comprobación hacia delante. Siempre que se asigne una variable X, el proceso de comprobación hacia delante mira cada variable no asignada Y que esté relacionada con X por una restricción y suprime del dominio de Y cualquier valor que sea inconsistente con el valor elegido para X. La Figura 5.6 muestra el progreso de una búsqueda, que colorea un mapa, con la comprobación hacia delante. Hay dos puntos importantes que debemos destacar sobre este ejemplo. Primero, notemos que después de asignar AO rojo y Q verde, los dominios de TN y AS se reducen a un solo valor; hemos eliminado las ramificaciones de estas variables totalmente propagando la información de AO y Q. La heurística MVR, la cual es una compañera obvia para la comprobación hacia delante, seleccionaría automáticamente AS y TN después. (En efecto, podemos ver la comprobación hacia delante como un modo eficiente de incrementar el cálculo de la información que necesita la heurística MVR para hacer su trabajo.) Un segundo punto a tener en cuenta es que, después de V azul, el dominio de SA está vacío. Por eso, la comprobación hacia delante ha descubierto que la asignación parcial {AO rojo, Q verde, V azul} es inconsistente con las restricciones del problema, y el algoritmo volverá atrás inmediatamente.
Aunque la comprobación hacia delante descubre muchas inconsistencias, no descubre todas. Por ejemplo, considere la tercera fila de la Figura 5.6. Muestra que cuando AO es rojo y Q es verde, tanto TN como AS están obligadas a ser azules. Pero son adyacentes y por tanto no pueden tener el mismo valor. La comprobación hacia delante no la descubre como una inconsistencia, porque no mira lo bastante lejos. La propagación de restricciones es el término general para la propagación de las implicaciones de una restricción sobre una variable en las otras variables; en este caso necesitamos propagar desde AO y Q a TN y AS, (como se hizo con la comprobación hacia delante) y luego a la restricción entre TN y AS para descubrir la inconsistencia. Y queremos hacer esto rápido: no es nada bueno reducir la cantidad de búsqueda si gastamos más tiempo propagando restricciones que el que hubiéramos gastado haciendo una búsqueda simple. La idea del arco consistente proporciona un método rápido de propagación de restricciones que es considerablemente más potente que la comprobación hacia delante. Aquí, «el arco» se refiere a un arco dirigido en el grafo de restricciones, como el arco de AS a NGS. Considerando los dominios actuales de AS y NGS, el arco es consistente si, para todo valor x de AS, hay algún valor y de NGS que es consistente con x. En la tercera fila de la Figura 5.6, los dominios actuales de AS y NGS son {azul} y {rojo, azul}, respectivamente. Para AS azul, hay una asignación consistente para NGS, a saber, NGS roja; por lo tanto, el arco de AS a NGS es consistente. Por otra parte, el arco inverso desde NGS a AS no es consistente: para la asignación NGS azul, no hay ninguna asignación consistente para AS. El arco puede hacerse consistente suprimiendo el valor azul del dominio de NGS. Podemos aplicar también el arco consistente al arco de AS a TN en la misma etapa del proceso de búsqueda. La tercera fila de la tabla en la Figura 5.6 muestra que ambas variables tienen el dominio {azul}. El resultado es que azul debe suprimirse del dominio de AS, dejando el dominio vacío. Así, la aplicación del arco consistente ha causado la detección temprana de una inconsistencia que no es descubierta por la comprobación hacia delante pura. La comprobación de la consistencia del arco puede aplicarse como un paso de preproceso antes de comenzar el proceso de búsqueda, o como un paso de propagación (como la comprobación hacia delante) después de cada asignación durante la búsqueda (a veces se llama a este último algoritmo MCA, Mantenimiento de la Consistencia del Arco). En uno u otro caso, el proceso debe aplicarse repetidamente hasta que no permanezcan 164 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO PROPAGACIÓN DE RESTRICCIONES ARCO CONSISTENTE más inconsistencias. Esto es porque, siempre que un valor se suprime del dominio de alguna variable para quitar una inconsistencia de un arco, una nueva inconsistencia de arco podría surgir en arcos que señalan a aquella variable. El algoritmo completo para la consistencia de arco, AC-3, utiliza una cola para guardar los arcos que tienen que comprobarse (véase la Figura 5.7). Cada arco (Xi , Xj ) se quita sucesivamente de la agenda y se comprueba; si cualquier valor requiere ser suprimido del dominio de Xi , entonces cada arco (Xk, Xi ) señalando a Xi debe ser reinsertado sobre la cola para su comprobación. La complejidad de la comprobación de consistencia de arco puede analizarse como sigue: un PSR binario tiene a lo más O(n2 ) arcos; cada arco (Xk, Xi ) puede insertarse en la agenda sólo d veces, porque Xi tiene a lo más d valores para suprimir; la comprobación de la consistencia de un arco puede hacerse en O(d2 ) veces; entonces el tiempo total, en el caso peor, es O(n2 d3 ). Aunque sea considerablemente más costoso que la comprobación hacia delante, el coste suplementario por lo general vale la pena1 . Como los PSRs incluyen a 3SAT como un caso especial, no esperamos encontrar un algoritmo de tiempo polinomial que puede decidir si un PSR es consistente. De ahí, deducimos que la consistencia de arco no revela todas las inconsistencias posibles. Por ejemplo, en la Figura 5.1, la asignación parcial {AO rojo, NGS rojo} es inconsistente, pero AC-3 no la encuentra. Las formas más potentes de la propagación pueden definirse utilizando la noción llamada k-consistencia. Un PSR es k-consistente si, para cualquier conjunto de k 1 variables y para cualquier asignación consistente a esas variables, siempre se puede asignar un valor consistente a cualquier k-ésima variable. Por ejemplo, la 1-consistencia significa que cada variable individual, por sí mismo, es consistente; también llamado consistencia de nodo. La 2-consistencia es lo mismo que la consistencia de arco. La 3-consistencia significa que cualquier par de variables adyacentes pueden siempre extenderse a una tercera variable vecina; también llamada consistencia de camino. Un grafo es fuertemente k-consistente si es k-consistente y también (k 1)-consistente, (k 2)-consistente..., hasta 1-consistente. Ahora supongamos que tenemos un PSR con n nodos y lo hacemos fuertemente n-consistente (es decir, fuertemente k-consistente para k n). Podemos resolver el problema sin vuelta atrás. Primero, elegimos un valor consistente para X1. Entonces tenemos garantizado el poder elegir un valor para X2 porque el grafo es 2-consistente, para X3 porque es 3-consistente, etcétera. Para cada variable Xi , tenemos sólo que averiguar los valores de d, en el dominio, para encontrar un valor consistente con X1..., Xi – 1. Tenemos garantizado encontrar una solución en O(nd). Desde luego, no tenemos ningún tiempo libre: cualquier algoritmo para establecer la n-consistencia debe llevar un tiempo exponencial en n, en el caso peor. Hay una amplia diferencia entre consistencia de arco y n-consistencia: ejecutar controles de consistencia fuerte llevará más tiempo, pero tendrá un efecto mayor en la reducción del factor de ramificación y en descubrir asignaciones parciales inconsistentes. Es posible calcular el valor k más pequeño tal que al ejecutar la k-consistencia asegura que el problema puede resolverse sin volver atrás (véase la Sección 5.4), pero a menudo es poco práctico. En la práctica, la determinación del nivel apropiado de comprobación de la consistencia es sobre todo una ciencia empírica.
Cierto tipo de restricciones aparecen con frecuencia en problemas reales y pueden manejarse utilizando algoritmos de propósito especial más eficientes que los métodos de propósito general descritos hasta ahora. Por ejemplo, la restricción Todasdif dice que todas las variables implicadas deben tener valores distintos (como en el problema criptoaritmético). Una forma simple de detección de inconsistencias para la restricción Todasdif trabaja como sigue: si hay m variables implicadas en la restricción, y si tienen n valores posibles distintos, y m n, entonces la restricción no puede satisfacerse. Esto nos lleva al algoritmo simple siguiente: primero, quite cualquier variable en la restricción que tenga un dominio con una sola posibilidad, y suprima el valor de esa variable de los dominios de las variables restantes. Repetir mientras existan variables con una sola posibilidad. Si en algún momento se produce un dominio vacío o hay más variables que valores en el dominio, entonces se ha descubierto una inconsistencia. Podemos usar este método para detectar la inconsistencia en la asignación parcial {AO rojo, NGS rojo} para la Figura 5.1. Notemos que las variables SA, TN y Q están efectivamente relacionadas por una restricción Todasdif porque cada par debe ser de un color diferente. Después de aplicar AC-3 con la asignación parcial, el dominio de cada variable se reduce a {verde, azul}. Es decir, tenemos tres variables y sólo dos colores, entonces se viola la restricción Todasdif. Así, un procedimiento simple de consistencia para una restricción de orden alto es a veces más eficaz que la aplicación de la consistencia de arco a un conjunto equivalente de restricciones binarias. 166 INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO CONSISTENCIA DE NODO CONSISTENCIA DE CAMINO FUERTEMENTE K-CONSISTENTE Quizá la restricción de orden alto más importante es la restricción de recursos, a veces llamada restricción como-máximo. Por ejemplo, PA1…, PA4 denotan los números de personas asignadas a cada una de las cuatro tareas. La restricción que no asigna más de 10 personas en total, se escribe como-máximo(10, PA1, PA2, PA3, PA4). Se puede descubrir una inconsistencia simplemente comprobando la suma de los valores mínimos de los dominios actuales; por ejemplo, si cada variable tiene el dominio {3, 4, 5, 6}, la restricción como-máximo no puede satisfacerse. También podemos hacer cumplir la consistencia suprimiendo el valor máximo de cualquier dominio si no es consistente con los valores mínimos de los otros dominios. Así, si cada variable, en nuestro ejemplo, tiene el dominio {2, 3, 4, 5, 6}, los valores 5 y 6 pueden suprimirse de cada dominio. Para problemas grandes de recursos limitados con valores enteros (como son los problemas logísticos que implican el movimiento de miles de personas en cientos de vehículos) no es, por lo general, posible representar el dominio de cada variable como un conjunto grande de enteros y gradualmente reducir ese conjunto por los métodos de comprobación de la consistencia. En cambio, los dominios se representan por límites superiores e inferiores y son manejados por la propagación de límites. Por ejemplo, supongamos que hay dos vuelos, 271 y 272, para los cuales los aviones tienen capacidades de 156 y 385, respectivamente. Los dominios iniciales para el número de pasajeros sobre cada vuelo son Vuelo271 [0,165] y Vuelo272 [0,385] Supongamos ahora que tenemos la restricción adicional que los dos vuelos juntos deben llevar a las 420 personas: Vuelo271 Vuelo272 [420,420]. Propagando los límites de las restricciones, reducimos los dominios a Vuelo271 [35,165] y Vuelo272 [255,385] Decimos que un PSR es consistente-acotado si para cada variable X, y tanto para los valores de las cotas inferior y superior de X, existe algún valor de Y que satisface la restricción entre X e Y, para cada variable Y. Esta clase de propagación de límitesse utiliza, ampliamente, en problemas restringidos prácticos.
El algoritmo de BÚSQUEDA-CON-VUELTA-ATRÁS de la Figura 5.3 tiene una política muy simple para saber qué hacer cuando falla una rama de búsqueda: hacia atrás hasta la variable anterior e intentar un valor diferente para ella. Se llama vuelta atrás cronológica, porque se visita de nuevo el punto de decisión más reciente. En esta subsección, veremos que hay muchos caminos mejores. Veamos lo que ocurre cuando aplicamos la vuelta atrás simple de la Figura 5.1 con una variable fija que ordena Q, NGS, V, T, AS, AO, TN. Supongamos que hemos generado la asignación parcial {Q rojo, NGS verde, V azul, T rojo}. Cuando intentamos la siguiente variable, AS, vemos que cada valor viola una restricción. ¡Volvemos hacia atrás hasta T e intentamos un nuevo color para Tasmania! Obviamente esto es inútil (el nuevo color de Tasmania no puede resolver el problema con Australia del Sur). Una aproximación más inteligente a la vuelta atrás es ir hacia atrás hasta el conjunto de variables que causaron el fracaso. A este conjunto se le llama conjunto conflicto; aquí, el conjunto conflicto para AS es {Q, NGS, V}. En general, el conjunto conflicto para la variable X es el conjunto de variables previamente asignadas que están relacionadas con X por las restricciones. El método salto-atrás retrocede a la variable más reciente en el conjunto conflicto; en este caso, el salto-atrás debería saltar sobre Tasmania e intentar un nuevo valor para V. Esto se implementa fácilmente modificando la BÚSQUEDA-CON-VUELTA-ATRÁS de modo que acumule el conjunto conflicto mientras comprueba un valor legal para asignar. Si no se encuentra un valor legal, debería devolver el elemento más reciente del conjunto conflicto con el indicador de fracaso. El lector habrá notado que la comprobación hacia delante puede suministrar el conjunto conflicto sin trabajo suplementario: siempre que la comprobación hacia delante, basada en una asignación a X, suprima un valor del dominio de Y, deberíamos añadir X al conjunto conflicto de Y. También, siempre que se suprima el último valor del dominio de Y, las variables en el conjunto conflicto de Y se añaden al conjunto conflicto de X. Entonces, cuando llegamos a Y, sabemos inmediatamente dónde volver atrás si es necesario. El lector habrá notado algo raro: el salto-atrás ocurre cuando cada valor de un dominio está en conflicto con la asignación actual; ¡pero la comprobación hacia delante descubre este acontecimiento y previene la búsqueda de alcanzar alguna vez tal nodo! De hecho, puede demostrarse que cada rama podada por el salto-atrás también se poda por la comprobación hacia delante. De ahí, el salto-atrás simple es redundante con una búsqueda de comprobación hacia delante o, en efecto, en una búsqueda que usa la comprobación de consistencia fuerte, como MCA. A pesar de las observaciones del párrafo anterior, la idea que hay detrás del saltoatrás sigue siendo buena: retroceder basándose en los motivos de fracaso. El salto-atrás se da cuenta del fracaso cuando el dominio de una variable se hace vacío, pero en muchos casos una rama es condenada mucho antes de que esto ocurra. Considere otra vez la asignación parcial {AO rojo, NGS rojo} (que, de nuestra discusión anterior, es inconsistente). Supongamos que intentamos T rojo después y luego asignamos a TN, Q, V, AS. Sabemos que no se puede hacer ninguna asignación para estas cuatro últimas variables, ya que finalmente nos quedamos sin valores para intentar en TN. Ahora, la pregunta es, ¿a dónde regresar? El salto-atrás no puede trabajar, porque TN tiene realmente valores consistentes con las variables precedentes adjudicadas (TN no tiene un conjunto conflicto completo de variables precedentes que hicieron que fallara). Sabemos, sin embargo, que las cuatro variables TN, Q, V, y AS, juntas, dan fallo debido a un conjunto de variables precedentes, que directamente entran en conflicto con las cuatro. Esto conduce a una noción más profunda del conjunto conflicto para una variable como TN: es ese conjunto de variables precedentes el que causa que TN, junto con cualquier variable siguiente, no tenga ninguna solución consistente. En este caso, el conjunto es AO y NGS, así que el algoritmo debería regresar a NGS y saltarse Tasmania. Al algoritmo de salto–atrás que utiliza los conjuntos conflicto definidos de esta manera se le llama salto-atrás dirigido-por-conflicto. Debemos explicar ahora cómo calculamos estos nuevos conjuntos conflictos. El método, de hecho, es muy simple. El fracaso «terminal» de una rama de búsqueda siempre ocurre porque el dominio de una variable se hace vacío; esa variable tiene un conjunto conflicto estándar. En nuestro ejemplo, AS falla, y su conjunto conflicto es {AO, TN, Q}. Saltamos atrás a Q, y Q absorbe el conjunto conflicto de AS (menos Q, desde luego) en su propio conjunto conflicto directo, que es {TN, NGS}; el nuevo conjunto conflicto es {AO, TN, NGS}. Es decir no hay ninguna solución de Q hacia delante, dada la asignación precedente a {AO, TN, NGS}. Por lo tanto, volvemos atrás a NT, el más reciente de éstos. TN absorbe {AO, TN, NGS} {TN} en su propio conjunto conflicto directo {AO}, dando {AO, NGS} (como en los párrafos anteriores). Ahora el algoritmo de salto atrás a NGS, como era de esperar. Resumiendo: sea Xj la variable actual, y sea conf(Xj ) su conjunto conflicto. Si para todo valor posible para Xj falla, saltamos atrás a la variable más reciente Xi , en conf(Xj ), y el conjunto conf(Xi ) ← conf(Xi ) conf(Xj ) {Xi } Salto-atrás dirigido-por-conflicto va hacia atrás al punto derecho en el árbol de búsqueda, pero no nos impide cometer los mismos errores en otra rama del árbol. Aprender la restricción realmente modifica el PSR añadiendo una nueva restricción inducida por estos conflictos.
ALos algoritmos de búsqueda local (véase la Sección 4.3) resultan ser muy eficaces en la resolución de muchos PSRs. Ellos utilizan una formulación de estados completa: el estado inicial asigna un valor a cada variable, y la función sucesor, por lo general, trabaja cambiando el valor de una variable a la vez. Por ejemplo, en el problema de las 8-reinas, el estado inicial podría ser una configuración arbitraria de ocho reinas en ocho columnas, y la función sucesor escoge a una reina y piensa en moverla a otra parte en su columna. Otra posibilidad sería comenzar con ocho reinas, una por columna, en una permutación de las ocho filas, y generaría a un sucesor tomando dos reinas que intercambian sus filas2 . Hemos visto ya, realmente, un ejemplo de búsqueda local para resolver un PSR: la aplicación de las ascensión de colinas al problema de n-reinas (página 126). Otra es la aplicación de SAT-CAMINAR (página 251) para resolver problemas de satisfacción, un caso especial de PSRs. En la elección de un nuevo valor para una variable, la heurística más obvia debe seleccionar el valor que cause el número mínimo de conflictos con otras variables (heurística de mínimos-conflictos). La Figura 5.8 muestra el algoritmo y en la Figura 5.9 se muestra su aplicación a un problema de 8-reinas, cuantificada en la Figura 5.5. Los mínimos-conflictos son sorprendentemente eficaces para muchos PSRs, en particular, cuando se ha dado un estado inicial razonable. En la última columna de la Figura 5.5 se muestra su funcionamiento. Extraordinariamente, sobre el problema de las nreinas, si no cuenta la colocación inicial de las reinas, el tiempo de ejecución de mínimos-conflictos es más o menos independiente del tamaño del problema. Resuelve hasta el problema de un millón de reinas en un promedio de 50 pasos (después de la asignación inicial). Esta observación notable fue el estímulo que condujo a gran parte de la investigación en los años 90 sobre la búsqueda local y la diferencia entre problemas fáciles y difíciles, los cuales veremos en el Capítulo 7. Hablando de forma aproximada, las n-reinas son fáciles para la búsqueda local porque las soluciones están densamente distribuidas en todas las partes del espacio de estados. Los mínimos-conflictos también trabajan bien para problemas difíciles. Por ejemplo, se han utilizado para programar las observaciones del Telescopio Hubble, reduciendo el tiempo utilizado para programar una semana de observaciones, de tres semanas (!) a alrededor de 10 minutos.Otra ventaja de la búsqueda local consiste en que puede usarse en un ajuste online cuando el problema cambia. Esto es particularmente importante en la programación de problemas. El programa de vuelos de una semana puede implicar miles de vuelos y decenas de miles de asignaciones de personal, pero el mal tiempo en un aeropuerto puede convertir a la programación en no factible. Nos gustaría reparar la programación con un número mínimo de cambios. Esto puede hacerse fácilmente con un algoritmo de búsqueda local comenzando desde el programa actual. Una búsqueda con vuelta atrás con un nuevo conjunto de restricciones, por lo general, requiere mucho más tiempo y podría encontrar una solución, desde el programa actual, con muchos cambios.
En esta sección, examinamos las formas por las cuales la estructura del problema, representada por el grafo de restricciones, puede utilizarse para encontrar soluciones de forma rápida. La mayor parte de estas aproximaciones son muy generales y aplicables a otros problemas, por ejemplo, razonamiento probabilístico. Después de todo, la única forma que podemos esperar, posiblemente, que pueda tratar con el mundo real es la descomposición en muchos subproblemas. Viendo de nuevo la Figura 5.1(b), con miras a identificar la estructura del problema, se destaca un hecho: Tasmania no está relacionada con el continente3 . Intuitivamente, es obvio que colorear Tasmania y colorear el continente son subproblemas independientes (cualquier solución para el continente combinado con cualquier solución para Tasmania produce una solución para el mapa entero). La independencia puede averiguarse simplemente buscando componentes conectados del grafo de restricciones. Cada componente corresponde a un subproblema PSRi . Si la asignación Si es una solución de PSRi , entonces i Si es una solución de i PSRi . ¿Por qué es tan importante? Consideremos lo siguiente: suponga que cada PSRi tiene c variables del total de n variables, donde c es una constante. Entonces hay nc subproblemas, cada uno de los cuales trae consigo como mucho dc de trabajo para resolverlo. De ahí, que el trabajo total es O(dc nc), que es lineal en n; sin la descomposición, el trabajo total es O(dn ), que es exponencial en n. Seamos más concretos: la división de un PSR booleano con n 80 en cuatro subproblemas con c 20 reduce el tiempo de resolución, en el caso peor, de la vida del universo hasta menos de un segundo. Los subproblemas completamente independientes son deliciosos, pero raros. En la mayoría de casos, los subproblemas de un PSR están relacionados. El caso más simple es cuando el grafo de restricciones forma un árbol: cualquiera dos variables están relacionadas por, a lo sumo, un camino. La Figura 5.10(a) muestra un ejemplo esquemático. Mostraremos que cualquier PSR estructurado por árbol puede resolverse en tiempo lineal en el número de variables. El algoritmo tiene los siguientes pasos: 1. Elija cualquier variable como la raíz del árbol, y ordene las variables desde la raíz a las hojas de tal modo que el padre de cada nodo en el árbol lo precede en el ordenamiento. (Véase la Figura 5.10(b).) Etiquetar las variables X1…, Xn en orden. Ahora, cada variable excepto la raíz tiene exactamente una variable padre. 2. Para j desde n hasta 2, aplicar la consistencia de arco al arco (Xi , Xj ), donde Xi es el padre de Xj , quitando los valores del DOMINIO[Xi ] que sea necesario. 3. Para j desde 1 a n, asigne cualquier valor para Xj consistente con el valor asignado para Xi , donde Xi es el padre de Xj . Hay dos puntos claves a destacar. Primero, después del paso 2 el PSR es directamente arco-consistente, entonces la asignación de valores en el paso 3 no requiere ninguna vuelta atrás. (Véase la discusión de k-consistencia de la página 167.) Segundo, aplicando la comprobación de consistencia de arco en orden inverso en el paso 2, el algoritmo asegura que cualquier valor suprimido no puede poner en peligro la consistencia de arcos que ya han sido tratados. El algoritmo completo se ejecuta en tiempo O(nd2 ). Ahora que tenemos un algoritmo eficiente para árboles, podemos considerar si los grafos restricción más generales pueden reducirse a árboles de alguna manera. Hay dos modos primarios de hacer esto, uno basado en quitar nodos y uno basado en nodos que sufren colisiones. La primera aproximación implica valores de asignación a algunas variables de modo que las variables restantes formen un árbol. Consideremos el grafo restricción para Australia, mostrado otra vez en la Figura 5.11(a). Si pudiéramos suprimir Australia del Sur, el grafo se haría un árbol, como en (b). Por suerte, podemos hacer esto (en el grafo, no en el continente) fijando un valor para AS y suprimiendo de los dominios de las otras variables cualquier valor que sea inconsistente con el valor elegido para AS. Ahora, cualquier solución para el PSR después de que AS y sus restricciones se quiten, será consistente con el valor elegido para AS. (Para los PSRs binarios, la situación es más complicada con restricciones de orden alto.) Por lo tanto, podemos resolver el árbol restante con el algoritmo anterior y así resolver el problema entero. Desde luego, en el caso general (a diferencia de colorear el mapa) el valor elegido para AS podría ser el incorrecto, entonces tendríamos que intentarlo con cada uno de ellos. El algoritmo general es como sigue: 1. Elegir un subconjunto S de VARIABLES[psr] tal que el grafo de restricciones se convierta en un árbol después del quitar S. Llamamos a S un ciclo de corte. 2. Para cada asignación posible a las variables en S que satisface todas las restricciones sobre S, (a) quitar de los dominios de las variables restantes cualquier valor que sea inconsistente con la asignación para S, y (b) si el PSR restante tiene una solución, devolverla junto con la asignación para S. Si el ciclo de corte tiene tamaño c, entonces el tiempo de ejecución total es O(dc (n c)d 2 ). Si el grafo es «casi un árbol» entonces c será pequeño y los ahorros sobre la vuelta atrás serán enormes. En el caso peor, sin embargo, c puede ser tan grande como (n 2). Encontrar el ciclo de corte más pequeño es NP-duro, pero se conocen varios algoritmos aproximados eficientes para esta tarea. A la aproximación algorítmica general se le llama acondicionamiento del corte que veremos de nuevo en el Capítulo 14, donde se usará para el razonamiento sobre probabilidades. La segunda aproximación está basada en la construcción de una descomposición en árbol del grafo restricción en un conjunto de subproblemas relacionados. Cada subproblema se resuelve independientemente, y las soluciones que resultan son entonces combinadas. Como la mayoría de los algoritmos divide-y-vencerás, trabajan bien si ninguno de los subproblemas es demasiado grande. La Figura 5.12 muestra una descomposición de árbol del problema que colorea un mapa en cinco subproblemas. Una descomposición de árbol debe satisfacer las tres exigencias siguientes: • Cada variable en el problema original aparece en al menos uno de los subproblemas. • Si dos variables están relacionadas por una restricción en el problema original, deben aparecer juntas (junto con la restricción) en al menos uno de los subproblemas. • Si una variable aparece en dos subproblemas en el árbol, debe aparecer en cada subproblema a lo largo del camino que une a esos subproblemas. Las dos primeras condiciones aseguran que todas las variables y las restricciones están representadas en la descomposición. La tercera condición parece bastante técnica, pero simplemente refleja la restricción de que cualquier variable debe tener el mismo valor en cada subproblema en el cual aparece; los enlaces que unen subproblemas en el árbol hacen cumplir esta restricción. Por ejemplo, AS aparece en los cuatro subproblemas de la Figura 5.12. Puede verificar de la Figura 5.11 que esta descomposición tiene sentido. Resolvemos cada subproblema independientemente; si alguno de ellos no tiene ninguna solución, sabemos que el problema entero no tiene ninguna solución. Si podemos resolver todos los subproblemas, entonces intentamos construir una solución global como sigue. Primero, vemos a cada subproblema como «una megavariable» cuyo dominio es el conjunto de todas las soluciones para el subproblema. Por ejemplo, los subproblemas más a la izquierda en la Figura 5.12 forman un problema que colorea el mapa con tres variables y de ahí que tienen seis soluciones (una es {AO rojo, AS azul, TN verde}). Entonces, resolvemos las restricciones que unen los subproblemas utilizando el algoritmo eficiente para árboles. Las restricciones entre subproblemas simplemente insisten en que las soluciones del subproblema deben estar de acuerdo con sus variables compartidas. Por ejemplo, considerando la solución {AO rojo, AS azul, TN verde} para el primer subproblema, la única solución consistente para el siguiente subproblema es {AS azul, TN verde, Q rojo}. El grafo de restricciones admite muchas descomposiciones en árbol; el objetivo en la elección de una descomposición, es hacer los subproblemas tan pequeños como sea posible. La anchura del árbol de una descomposición en árbol de un grafo es menor que el tamaño del subproblema más grande; la anchura de árbol del grafo en sí mismo está definida por la anchura de árbol mínimo entre todas sus descomposiciones en árbol. Si un grafo tiene la anchura de árbol w, y nos dan la descomposición en árbol correspondiente, entonces el problema puede resolverse en O(nd w 1 ) veces. De ahí que, los PSRs con grafos de restricciones de anchura de árbol acotada son resolubles en tiempo polinomial. Lamentablemente, encontrar la descomposición con la anchura del árbol mínima es NP-duro, pero hay métodos heurísticos que trabajan bien en la práctica.